import LocalGraph as Graph
import AnalyzeFile as Analyzer  
import re
import time
import os.path

fileName = None
metaFile = []
def ParserSelectFile(filename):    
    global fileName 
    fileName= filename     
def seekNode(node):
    'Open the file which exists, checked from PaserSelectFile'    
    tempFile = open(fileName)
    
    'Check metafile to perform almost instant searches'
    tempFile.seek(int(getPosition(node)))
    'Seek the node you are searching for'
    lines = []
    p = re.compile('^'+node+'   |   '+node+'   ')
    while 1:
        line = tempFile.readline()
        if(not line):
            return
        if(p.match(line)!=None):
            lines.append(line)
            lines.append(tempFile.readline())
            break            
    tempFile.close()
    return lines

def seekNodeLite(node):
    "This version only finds nodes at the beginnings of lines."
    tempFile = open(fileName)
    tempFile.seek(int(getPosition(node)))
    lines = []
    p = re.compile('^'+node+'   ')    
    while 1:
        line = tempFile.readline()
        if(not line):
            return
        if(p.match(line)!=None):
            lines.append(line)
            lines.append(tempFile.readline())
            break
    tempFile.close()
    return lines

def initMetaFile():
    global metaFile
    global fileName
    metaFile = []
    if(os.path.isfile(fileName+".meta")):
        print "Metafile found, loading metafile"
        inFile = open(fileName+".meta")
    else:
        print "Metafile not found, creating meta and single file. Please wait..."    
        Analyzer.AnalyzeFile(fileName)
        print "metafile made, loading..."
        inFile = open(fileName+".meta")
    while 1:
        l = inFile.readline()
        if(not l):
            break
        elts = l.strip().split(":")
        metaFile.append([elts[0],elts[1]])
    
def getPosition(node):
    global metaFile    
    chunk = len(metaFile)
    return getPosRecurser(node,chunk/2,chunk/2)
    
def getPosRecurser(node,pos,chunk):
    global metaFile    
    if(metaFile[pos][0]==node):
        return metaFile[pos][1]
    elif(chunk==0):        
        if(pos == 0 or pos == len(metaFile)-1):
            return metaFile[pos][1]
        if(node>=metaFile[pos-1][0] and node<=metaFile[pos+1][0]):            
            return metaFile[pos-1][1]
        elif(node<metaFile[pos-1][0]):            
            return getPosRecurser(node,pos-1,0)
        else:            
            return getPosRecurser(node,pos+1,0)
    elif(node<metaFile[pos][0]):
        return getPosRecurser(node,pos-chunk/2,chunk/2)
    else:
        return getPosRecurser(node,pos+chunk/2,chunk/2)

       

def GetUnreciprocated(node,flag=0):
    'If fileName has not been specified, return -1'
    if fileName == None:
        return -1        
    
    lines = seekNodeLite(node)
        
    'If l1 = None, then node does not exist in here. Return error'
    if(len(lines)<2):
        return -1
    
    'split the lines into parseable forms'
    l1 = lines[0].strip().split()
    l2 = lines[1].strip().split()
    
    'Determine incoming and outgoing relations, this basically selects only the incoming or outgoing part of the data'
    outgoing = set(l1[3:-1])
    incoming = set(l2[3:-1])        
    
    retValue = []        
    if flag == 0:
        'All unreciprocated'
        retValue+=list(outgoing.difference(incoming))
        retValue+=list(incoming.difference(outgoing))    
    
    elif flag == 1:
        'Incoming that is not reciprocated'        
        retValue+=incoming.difference(outgoing)
        
    elif flag == 2:
        'Outgoing that is not reciprocated'
        retValue+=outgoing.difference(incoming)
    
    return retValue

def CreateLocalGraph(node1,node2,depth=4,needConnection=True, maxNodes=float('inf'), maxStartingEdges=float('inf')):
    'Create a graph'
    createdGraph = Graph.LocalGraph(node1,node2,depth,fileName)
        

    'Search for the two nodes'
    n1=seekNodeLite(node1)
    n2=seekNodeLite(node2)    
    #if not (n1[0].startswith(node1+'   0')):
    #    print node1, n1
    #    raise Exception('Bad assumption')
    #if not (n1[1].startswith(node1+'   1')):
    #    print node1, n1
    #    raise Exception('Bad assumption')
    #if not (n2[0].startswith(node2+'   0')):
    #    print node2, n2
    #    raise Exception('Bad assumption')
    #if not (n2[1].startswith(node2+'   1')):
    #    print node2, n2
    #    raise Exception('Bad assumption')
    
    n1out = n1[0].strip().split("   ")
    n1in = n1[1].strip().split("   ")
    
    n2out = n2[0].strip().split("   ")
    n2in = n2[1].strip().split("   ")         
    edgeCount = len(set(n1out[3:-1]).union(set(n1in[3:-1]).union(set(n2out[3:-1]).union(set(n2in[3:-1])))))
    if edgeCount > maxStartingEdges:
        return None
    'Create outgoing relationship'
    createdGraph.Outgoing[int(n1out[0])] = [int(x) for x in n1out[3:-1]]
    createdGraph.Outgoing[int(n2out[0])] = [int(x) for x in n2out[3:-1]]
    
    'Create incoming relationship'
    createdGraph.Incoming[int(n1in[0])] = [int(x) for x in n1in[3:-1]]
    createdGraph.Incoming[int(n2in[0])] = [int(x) for x in n2in[3:-1]]
        
    'Add to expand node'
    ExpandNodes = set([int(n1in[0]),int(n2in[0]),int(n1out[0]),int(n2out[0])])
    ExpandNodes.update([int(x) for x in n1in[3:-1]])
    ExpandNodes.update([int(x) for x in n2in[3:-1]])
    ExpandNodes.update([int(x) for x in n1out[3:-1]])
    ExpandNodes.update([int(x) for x in n2out[3:-1]])
    
    
    
    curDepth = 0
    'Depth iterator'
    while curDepth<depth:
        curDepth+=1
        tempNodes = set()
        'For all nodes in ExpandNodes, expand graph by a single depth'
        done = False
        for x in ExpandNodes:            
            if len(createdGraph.Nodes) >= maxNodes:
                done = True
                break
            'Check to see the node is already not included in the graph'
            if not (x in createdGraph.Nodes):
                'Include to nodes involved'
                #print 'adding', x
                createdGraph.Nodes.add(x)
                
                'Seek the node'
                n = seekNodeLite(str(x))
                if(n==None):
                    continue
                #if not (n[0].startswith(str(x)+'   0')):
                #    print x, n
                #    raise Exception('Bad assumption')
                #if not (n[1].startswith(x+'   1')):
                #    print x, n
                #    raise Exception('Bad assumption')

                nin = n[0].strip().split("   ")
                nout = n[1].strip().split("   ")
                'Create ougoing and incoming relationship'
                createdGraph.Outgoing[int(nout[0])] = [int(x) for x in nout[3:-1]]
                createdGraph.Incoming[int(nin[0])] = [int(x) for x in nin[3:-1]]
                
                'Add to tempNodes'
                tempNodes.update([int(x) for x in nout[3:-1]])
                tempNodes.update([int(x) for x in nin[3:-1]])
        if done:
            return None
        'Set tempNodes and the next ExpandNodes'
        ExpandNodes = tempNodes
    
    return createdGraph
        
        
"""Code goes here"""
""""""
""""""
""""""""""""""""""
'''
Steps you must go through

1. select file by doing ParserSelectFile(FileName)
2. initMetaFile()
3. create graph
4. Work with graph
Example below
'''

'''
In the .single file, lines are "src:dst1,dst2,..."
'''
'''
snapshot1 = '..\data\graph-2011-07-04.txt'
snapshot2 = '..\data\graph-2011-08-03.txt'

ParserSelectFile(snapshot1)
initMetaFile()
#g1 = CreateLocalGraph('100000003530958471380', '100000003530958471380', 0)
#g1 = CreateLocalGraph('100000036543200098866', '100000036543200098866', 0)
ParserSelectFile(snapshot2)
initMetaFile()
#g2 = CreateLocalGraph('100000003530958471380', '100000003530958471380', 0)
#g2 = CreateLocalGraph('100000036543200098866', '100000036543200098866', 0)


#sfile1 = open(snapshot1+'.single', 'r')
#numlines = 0
#for line in sfile1:
#  numlines += 1
#print str(numlines)
sfile1 = open(snapshot1+'.single', 'r')
#sfile2 = open(snapshot2+'.single', 'r')
#dfile2 = open(snapshot2+'.double', 'r')

count = 0
progress = 0

for line in sfile1:
  progress += 1
  if progress % 1000 == 0:
    print 'Line ', progress
  if line is '':
    continue
  line = line.split(':')
  src = line[0]
  dsts = [] if line[1] is '' else line[1].split(',')
  ParserSelectFile(snapshot1)
  initMetaFile()
  try:
    g1 = CreateLocalGraph(src, src, 0)
  except:
    continue # src node is invisible -> abort.
  
  ParserSelectFile(snapshot2)
  initMetaFile()
  try:
    g2 = CreateLocalGraph(src, src, 0)
    srcFound = True
  except:
    print 'src went private. Trying dsts...'
    srcFound = False
    g2s = {}
    for dst in dsts:
      try:
        g2s[dst] = CreateLocalGraph(dst, dst, 0)
      except:
        continue # Both nodes went private.
  
  
  for dst in dsts:
    if srcFound:
      reciprocated = dst in g2.Incoming[src]
    elif dst in g2s:
      reciprocated = src in g2s[dst].Outgoing[dst]
    else:
      continue # Both nodes went private -> abort.
    
    if reciprocated:
      count += 1

#print g1.Incoming['100000036543200098866']
#print g1.Outgoing['100000036543200098866']
        


print count, ' edges were reciprocated.'




#madeGraph = CreateLocalGraph('100000003530958471380','100000003530958471380',1)
#print madeGraph.Incoming
#raw_input("Paused!")
#print g2.Incoming['100000003530958471380']
#print g2.Outgoing['100000003530958471380']
        
    
#output to file, run perceptron on the file(s)
'''
